/*
 * @Author: szx
 * @Date: 2021-10-29 13:09:11
 * @LastEditTime: 2021-10-29 13:21:28
 * @Description:
 * @FilePath: \leetcode\350\350.cpp
 */
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// class Solution {
//    public:
//     vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//         sort(nums1.begin(), nums1.end());
//         sort(nums2.begin(), nums2.end());
//         vector<int> v;
//         int n1 = nums1.size();
//         int n2 = nums2.size();
//         int i = 0, j = 0;
//         while (i < n1 && j < n2) {
//             if (nums1[i] == nums2[j]) {
//                 v.push_back(nums1[i]);
//                 i++;
//                 j++;
//             } else if (nums1[i] > nums2[j]) {
//                 j++;
//             } else {
//                 i++;
//             }
//         }
//         return v;
//     }
// };

class Solution {
   public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);
        }
        unordered_map<int, int> m;
        for (int num : nums1) {
            ++m[num];
        }
        vector<int> intersection;
        for (int num : nums2) {
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }
};

int main() {}